/**
 * This file is released under the GNU General Public License.
 * Refer to the COPYING file distributed with this package.
 *
 * Copyright (c) 2008-2009 WURFL-Pro srl
 */
package net.sourceforge.wurfl.core.handlers.matchers.strategy;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.SortedSet;

import org.apache.commons.lang.text.StrBuilder;
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

/**
 * Singleton class applying RIS matcher strategy.
 * <p>
 * Searches for the string which has the longest common substring with the given
 * key
 * </p>
 * 
 * @author WURFL-PRO SRL, Rome, Italy
 * @version $Id: RISMatcher.java 1045 2009-03-09 15:52:53Z filippo.deluca $
 */
public class RISMatcher implements StringMatcher {

	/** Singleton instance */
	public static final RISMatcher INSTANCE = new RISMatcher();

	/** Log */
	private static final Log log = LogFactory.getLog(RISMatcher.class);

	/** private constructor, to avoid instantiate */
	private RISMatcher() {
		// Empty
	}
	
	// TODO extract to interface
	public String getName() {
		
		return "RIS";
	}

	/**
	 * Searches for the string which has the longest common substring with the
	 * given needle. If there is not candidates within given tolerance, it
	 * returns null.
	 * 
	 * @param candidates
	 *            The SortedSet of possible candidates.
	 * @param needle
	 *            The String to match.
	 * @param tolerance
	 *            the tolerance between needle and candidates.
	 * 
	 * @return Matched candidate String.
	 */
	public String match(SortedSet/*String*/ candidates, String needle, int tolerance)
    {
        
		if (log.isTraceEnabled()) {
			StrBuilder sb = new StrBuilder("Applying RIS(");
			sb.append(tolerance).append(") on: ");
			sb.append(needle).append(" with candidates: [");
			for (Iterator uIt = candidates.iterator(); uIt.hasNext();) {
				sb.append(uIt.next());

				if (uIt.hasNext()) {
					sb.append(", ");
				}
			}
			sb.append("]");

			log.trace(sb.toString());
		}
		
		String match = null;
		
		int needleLength = needle.length();
		List/*String*/ candidatesList = new ArrayList(candidates);
        
		String bestMatch = null;
		double bestDistance = -1;

        int low = 0;
        int high = candidatesList.size() - 1;

        /* 
         * Perfect match: bestDistance == needle.lenght()
         * Best match: bestDistance >= tolerance
         * First match: bestDistance == tolerance
         */
        while (low <= high && bestDistance<needleLength){
            int mid = (low + high) / 2;
            String midCandidate = (String)candidatesList.get(mid);

            int distance = getDistance(needle, midCandidate);
            if (distance > bestDistance){
            	bestMatch = midCandidate;
                bestDistance = distance;
            }
            
            // Calculate low and high
            int cmp = midCandidate.compareTo(needle);
            if (cmp < 0) {
                low = mid + 1;
            }
            else if (cmp > 0){
                high = mid - 1;
            }
            else{
                break;
            }
        }

        // Candidate is found
        if (bestDistance >= tolerance) {
            match = bestMatch;
			
            if (log.isTraceEnabled()) {
				log.trace("Found match: " + match);
			}
        }

        return match;
    }
	
	private static int getDistance(String t1, String t2){
        
		int t = Math.min(t1.length(), t2.length());
        int i = 0;
        
        while (i < t && t1.charAt(i) == t2.charAt(i)){
            i++;
        }
        
        return i;
    }

	public String toString() {

		return getName();
	}
}
